Field of the Disclosure
This disclosure relates generally to concurrent data structures, and more particularly to systems and methods for constructing persistent data structures that are composable and that adhere to a “strict failure resilience” correctness condition.
Description of the Related Art
Persistent memory technologies such as phase change memory, spin-transfer torque magnetoresistive RAM, memristors, etc., are making inroads into the computing industry. These technologies are expected to come close to matching or even exceeding the performance of DRAM (100-1000× faster than state-of-the-art NAND flash) in the future. In some cases, these persistent memories are byte-addressable (as opposed to the block-addressable nature of disks and flash memory), which enables a move toward integrating non-volatile memories in systems on the memory bus, rather than only across an I/O interface.
Byte-addressability lends itself to a traditional memory (DRAM) style load/store interface to persistent memory. However, many components in the traditional memory hierarchy (e.g. processor caches, memory controller buffers) are expected to be non-persistent in the foreseeable future. Consequently, merely having a load/store interface is not sufficient to ensure persistence. There are existing proposals to augment processors with different cache line flush instructions and persist barrier instructions. In order to leverage the persistence feature of persistent memory, existing software and algorithms for in-memory data access would need to change to account for the attributes of systems that host persistent memory. Research activities in this area include those directed to file systems, programming models, and databases that reflect these differences. These differences are also reflected in some of the existing work being done in the area of persistent data structures. In general, the existing work falls in two categories: (i) the use of memory transactions, which make the solution simple, but which are accompanied by significant bookkeeping overhead, and (ii) the use of ad hoc data structures that appear to work correctly in isolation, but which can incur data losses due to failures at operation boundaries. For example, in a persistent stack, if a failure occurs immediately before a Pop( ) operation returns but after it has persisted, the returned value could be lost.
Some of this existing work (particularly that described by Venkataraman, et al.) addresses the question of correctness conditions for persistent concurrent data structures that builds on the classic linearizability correctness condition for concurrent data structures. While this is a good start, this work does not address the important aspect of composability of data structure operations. Thus, the approach described by Venkataraman, et al. has some serious implications on application correctness. For example, when failures occur at the boundaries of data structure operations, the effects of an operation could be entirely lost.
While the disclosure is described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the disclosure is not limited to embodiments or drawings described. It should be understood that the drawings and detailed description hereto are not intended to limit the disclosure to the particular form disclosed, but on the contrary, the disclosure is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. Any headings used herein are for organizational purposes only and are not meant to limit the scope of the description or the claims. As used herein, the word “may” is used in a permissive sense (i.e., meaning having the potential to) rather than the mandatory sense (i.e. meaning must). Similarly, the words “include”, “including”, and “includes” mean including, but not limited to.